#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include<string.h>
#include<stdlib.h>

void HeapPrint(int* a, int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void CreatNode()
{
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{
		perror("fopen failed!\n");
		return;
	}
	int n = 100;
	srand((unsigned)time(NULL));
	for (int i = 0; i < n; i++)
	{
		int x = rand() % 10000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void PrintTopk(const char* file, int k)
{
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc failed!\n");
		return;
	}
	FILE* fin = fopen(file, "r");
	for (int i = 0; i < k; i++)
	{
		fscanf(fin, "%d", &minHeap[i]);
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, k, i);
	}
	int x = 0;
	while (fscanf(fin, "%d", &x) != EOF)
	{
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			AdjustDown(minHeap, k, 0);
		}
	}
	HeapPrint(minHeap, k);
	free(minHeap);
	fclose(fin);
}

void testTopk()
{
	//CreatNode();
	PrintTopk("data.txt", 5);
}

//
//void HeapSort(int* a, int n)
//{
//	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdjustDown(a, n, i);
//	}
//	int end = n - 1;
//	while (end > 0)
//	{
//		Swap(&a[0], &a[end]);
//		AdjustDown(a, end, 0);
//		end--;
//	}
//}

int main() 
{
	/*int a[] = { 3,5,87,5,3,9,1,6 };
	int	n = sizeof(a) / sizeof(a[0]);
	HeapSort(a, n);
	HeapPrint(a, n);*/
	testTopk();
	return 0;
}